package mo.tags.twopointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class L18 {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        for (int a = 0; a <= len-4; a++) {
            if (a > 0 && nums[a] == nums[a-1]) {
                continue;
            }
            for (int b = a+1; b <= len-3; b++) {
                if (b > a+1 && nums[b] == nums[b-1]) {
                    continue;
                }
                int c = b+1;
                int d = len - 1;
                while (c < d) {
                    long cur = (long) nums[a] + (long) nums[b] + (long) nums[c] + (long) nums[d];
                    if (cur == target) {
                        res.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                        c++;
                        d--;
                        while (c < d && nums[c] == nums[c-1]) {
                            c++;
                        }
                        while (c < d && nums[d] == nums[d+1]) {
                            d--;
                        }
                    } else if (cur < target) {
                        c++;
                    } else {
                        d--;
                    }
                }
            }
        }
        return res;
    }


    //[1000000000,1000000000,1000000000,1000000000]
    //-294967296
    public static void main(String[] args) {
        L18 test = new L18();
        System.out.println(test.fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, 0));
    }
}
